#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/4/23 14:30
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : qksort.py
# @Software: PyCharm

"""  
qksort
TODO模块说明
Public Class:
-	TODO类名: TODO类说明 
Public Methods: 
-	TODO方法名: TODO方法说明
"""
from random import randint
from time import time


def qsort(data, l, r):
    if l >= r:
        return
    i, j, h = l, r, (l + r) // 2
    x, data[h] = data[h], data[i]
    while i < j:
        while i < j and data[j] >= x:
            j -= 1
        if i < j:
            data[i] = data[j]
            i += 1
        while i < j and data[i] < x:
            i += 1
        if i < j:
            data[j] = data[i]
            j -= 1
    data[i] = x
    qsort(data, l, i - 1)
    qsort(data, i + 1, r)


def qsort_test(n):
    # a = [3, 4, 2, 1, 6]
    # n = 100000
    a = []
    for i in range(n):
        a.append(randint(0, n * 10))
    # print(a)
    t1 = int(time() * 1000)
    qsort(a, 0, len(a) - 1)
    t2 = int(time() * 1000)
    # print(a)
    p = True
    for i in range(n - 1):
        if a[i] > a[i + 1]:
            p = False
            break
    print('n=%d,%s' % (n, p))
    print(t2 - t1, 'ms')


def main():
    n = [10, 100, 1000, 10000, 50000, 100000, 100000, 500000]
    for x in n:
        qsort_test(x)


if __name__ == '__main__':
    main()
